package 力扣._188_买卖股票的最佳时机4;

public class Solution {
    public int maxProfit(int k, int[] prices) {
        //dp[i][0]: 无操作
        //dp[i][2*j-1]: 第i天第 j 次持有的最大现金
        //dp[i][2*j]:   第i天第 j 次不持有的最大现金  (第一次卖出后的不持有，在此之前的不持有为无操作)
        //滚动数组，从右向左遍历
        int[] dp = new int[1 + 2 * k];
        //初始化
        for (int i = 1; i < dp.length; i += 2) {
            dp[i] = -prices[0]; //第一天的第i/2次持有
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j < dp.length; j += 2) {
                //第j/2次不持有，= max(昨天第j/2-1不持有的最大钱数, 昨天的第j/2-1次持有卖掉)
                dp[j+1] = Math.max(dp[j+1], dp[j] + prices[i]);
                //第j/2次持有 = max(昨天的第j/2 -1 次持有今天卖掉，并买入， 昨天的第j/2-1次持有)
                dp[j] = Math.max(dp[j], dp[j-1] - prices[i]);
            }
        }
        return dp[2 * k];
    }

    public static void main(String[] args) {
        int i = new Solution().maxProfit(1, new int[]{1, 2});
        System.out.println(i);

    }
}
